package site.wanjiahao.sort.uncompare;

import site.wanjiahao.sort.Sort;

// 计数排序
public class CountingSort2 extends Sort<Integer> {


    @Override
    protected void sort() {
        int max = array[0];
        int min = array[0];
        for (int e: array) {
            if (e > max) {
                max = e;
            }
            if (e < min) {
                min = e;
            }
        }
        int[] counts = new int[max - min + 1];
        // 存入计数
        for (int e: array) {
            int index = e - min;
            counts[index] += 1;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        int[] output = new int[array.length];
        // 遍历数组元素
        for (int i = array.length - 1; i >= 0 ; i--) {
            int cur = array[i];
            output[--counts[cur - min]] = cur;

        }

        for (int i = 0; i < array.length; i++) {
            array[i] = output[i];
        }
    }

}
